package com.leetcode.题库;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-04-29 16:31
 */
public class 题库_0173_二叉搜索树迭代器 {

  static
  class BSTIterator {

    private final Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
      this.stack = new ArrayDeque<>();
      while (root != null) {
        this.stack.push(root);
        root = root.left;
      }
    }

    public int next() {
      TreeNode node = this.stack.pop();
      TreeNode root = node.right;
      while (root != null) {
        this.stack.push(root);
        root = root.left;
      }
      return node.val;
    }

    public boolean hasNext() {
      return !this.stack.isEmpty();
    }
  }

}
